#include <iostream>

using namespace std;

template<typename T>
class MyVector
{
    template<typename U>
    friend std::ostream& operator<<(std::ostream& out, const MyVector<U>& data);//友元函数
public:
    MyVector(int size = 2);
    ~MyVector();

    // 访问
    T& at(int index) const;
    T& front() const;
    T& back() const;
    T& operator[](int index);

    // 容量
    bool empty() const;
    int size() const;
    int capacity() const;

    // 修改
    void clear();
    void insert(int index, const T& d);
    void remove(int index);
    void push_back(const T& d);
    void pop_back();

private:
    void alloc();

private:
    T* data;
    int length;
    int current_pos;
};


/**
 * 类外实现模板函数注意：
 * 1. 需要使用 template<typename T>
 * 2. 要添加类名并且带模板参数 MyVector<T>::
*/
template<typename T>
MyVector<T>::MyVector(int size) : data(nullptr), length(size), current_pos(0)
{
    /**
     * 申请数据空间时时声明 T 数据类型的指针数组
    */
    data = new T[length];
}

template<typename T>
MyVector<T>::~MyVector()
{
    clear();
}

template<typename T>
void MyVector<T>::clear()
{
    if(data == nullptr)
        return;
    delete [] data;
    data = nullptr;
}

template<typename T>
T& MyVector<T>::at(int index) const
{
    if(index < 0 || index >= current_pos) {
        std::string str = "out of range, index should be in " + std::to_string(0) + " ~ " + std::to_string(current_pos);
        throw str.c_str();
    }
    return data[index];
}

template<typename T>
T& MyVector<T>::front() const
{
    if(empty()) {
        throw "vector is empty.";
    }
    return data[0];
}

template<typename T>
T& MyVector<T>::back() const
{
    if(empty()) {
        throw "vector is empty.";
    }
    return data[current_pos - 1];
}

template<typename T>
T& MyVector<T>::operator[](int index)
{
    if(index < 0 || index >= current_pos) {
        std::string str = "out of range, index should be in " + std::to_string(0) + " ~ " + std::to_string(current_pos);
        throw str.c_str();
    }
    return data[index];
}


template<typename T>
bool MyVector<T>::empty() const
{
    return current_pos == 0;
}

template<typename T>
int MyVector<T>::size() const
{
    return current_pos;
}

template<typename T>
int MyVector<T>::capacity() const
{
    return length;
}

template<typename T>
void MyVector<T>::insert(int index, const T& d)
{
    /**
     * 1. 当前 capacity 是否已经到达最大
     * 2. 如果 capacity 已经最大，需要给当前的 capacity 扩容
     * 3. index 边界检查
     * 4. 先移动数据，再插入数据
     * 5. size + 1
    */
    if(current_pos == length) {
       alloc();
    }

    if(index < 0 || index >= current_pos) {
        std::string str = "out of range, index should be in " + std::to_string(0) + " ~ " + std::to_string(current_pos);
        throw str.c_str();
        return;
    }

    /*
    ------------------------------------------------------------------
    |  1 |  2 |  3 |  4 |  5 |  6 |   |   |   |   |   |   |   |   |
    ------------------------------------------------------------------
    */
   // 该拷贝方式在插入是存在问题
    // memcpy(data + index, data + index + 1, (current_pos - index + 1) * sizeof(T));
    for(int i = current_pos; i >= index; i--) {
        data[i] = data[i - 1];
    }
    data[index] = d;

    ++current_pos;
}

template<typename T>
void MyVector<T>::remove(int index)
{
    /**
     * 1. index 边界检查
     * 2. 将 index 后数据直接往前移动，覆盖原有数据
     * 3. size - 1
     */
    if(index < 0 || index >= current_pos) {
        std::string str = "out of range, index should be in " + std::to_string(0) + " ~ " + std::to_string(current_pos);
        throw str.c_str();
        return;
    }

    /*
    ------------------------------------------------------------------
    |  1 |  2 |  3 |  4 |  5 |  6 |   |   |   |   |   |   |   |   |
    ------------------------------------------------------------------
    */
    // memcpy(data + index + 1, data + index, (current_pos - index + 1) * sizeof(T));
    for(int i = index; i < current_pos; i++) {
        data[i] = data[i + 1];
    }

    --current_pos;
}

template<typename T>
void MyVector<T>::push_back(const T& d)
{
    /**
     * 1. 当前 capacity 是否已经到达最大
     * 2. 如果 capacity 已经最大，需要给当前的 capacity 扩容
     * 3. 将数据放在数组最后
     * 4. size + 1
    */
    if(current_pos == length) {
       alloc();
    }

    data[current_pos] = d;

    ++current_pos;
}

template<typename T>
void MyVector<T>::pop_back()
{
    if(empty()) {
        throw "vector is empty.";
        return;
    }
    --current_pos;
}


template<typename T>
void MyVector<T>::alloc()
{
    /**
     * 扩容：
     * 1. 开辟出一块新内存（比原来内存大）
     * 2. 将原有的数据复制到新开辟的内存中
     *      1. 将里面数据一个一个复制
     *      2. 可以直接复制整块内存数据
     * 3. 将原来内存释放点
     * 4. 将新内存指针指向原指针
    */
    int len = length * 2;
    T* temp = new T[len];

    // for(int i = 0; i < current_pos; i++)
    //     temp[i] = data[i];
    memcpy(temp, data, current_pos * sizeof(T));
    
    clear();

    data = temp;

    length = len;
}

template<typename T>
std::ostream& operator<<(std::ostream& out, const MyVector<T>& data)
{
    out << "MyVector(";
    for(int i = 0; i < data.size(); i++) {
        if(i + 1 == data.size())
            out << data.at(i);
        else
            out << data.at(i) << ", ";
    }
    out << ")\n";
    return out;
}

int main(){
    
    MyVector<int> vec;
    vec.push_back(1);
    vec.push_back(2);
    vec.push_back(3);
    vec.push_back(4);
   cout<< vec.size()<<endl;
    vec.pop_back();
   cout<< vec.back()<<" "<< vec.front()<<endl;
    vec.insert(2,9);
   cout<< vec.at(2)<<endl;
    vec.remove(9);
    vec.clear();

   return 0;
}